import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 *  
 * <p>
 * 示例：
 * <p>
 * 输入：n = 3
 * 输出：[
 * "((()))",
 * "(()())",
 * "(())()",
 * "()(())",
 * "()()()"
 * ]
 */
class Solution {

    public static void main(String[] args) {
        List<String> strings = generateParenthesis2(3);
        for (String string : strings) {
            System.out.println(string);
        }

    }

    private static Map<Integer, List<String>> map = new HashMap<>();

    /**
     * 用递归的思想来想，n对的组合肯定是n-x对的组合组成的
     *
     * @param n
     * @return
     */
    public static List<String> generateParenthesis(int n) {
        if (map.containsKey(n)) return map.get(n);
        List<String> result = new ArrayList<>();
        if (n <= 0) {
            return result;
        }
        if (n == 1) {
            result.add("()");
            return result;
        }
        Set<String> set = new HashSet<>();
        List<String> pre = generateParenthesis(n - 1);
        for (String s : pre) {
            set.add("(" + s + ")");
            set.add("()" + s);
            set.add(s + "()");
        }
        for (int i = 2; i < n - 1; i++) {
            List<String> left = generateParenthesis(i);
            List<String> right = generateParenthesis(n - i);
            for (String leftString : left) {
                for (String rightString : right) {
                    set.add(leftString + rightString);
                }
            }
        }
        result = new ArrayList(set);
        map.put(n, result);
        return result;
    }

    /**
     * 利用回溯的算法
     *
     * @param n
     * @return
     */
    public static List<String> generateParenthesis2(int n) {
        List<String> ans = new ArrayList();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }

    public static void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }

        if (open < max) {
            cur.append('(');
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }

}
